def memoized_matrix_chain(p,i,j,m,s):
    if (i,j) in m:
        return m[i,j]
    elif i==j:
        m[i,j]=0
        s[i,j]=i
        return m[i,j]
    else:
        for k in range(i,j):
            q=memoized_matrix_chain(p,i,k,m,s)+\
               memoized_matrix_chain(p,k+1,j,m,s)+p[i]*p[k+1]*p[j+1]
            if (i,j) not in m or q<m[i,j]:
                m[i,j]=q
                s[i,j]=k
        return m[i,j]
def do_memoized_matrix_chain(p,m,s):
    n=len(p)-1
    memoized_matrix_chain(p,0,n-1,m,s)
def print_optimal_parens(s,i,j):
    if i==j:
        print i,
    else:
        print '(',
        print_optimal_parens(s,i,s[i,j])
        print_optimal_parens(s,s[i,j]+1,j)
        print ')',
def do_print_optimal_parens(s,n):
    print_optimal_parens(s,0,n-1)
    print
def print_ms(x,n):
    width=len(str(x[0,n-1]))
    print
    for l in xrange(n,0,-1):
        for i in xrange(n-l+1):
            j=i+l-1
            print '{0:{w}}'.format(x[i,j],w=width),
        print
    
if __name__=='__main__':
    p=[30,35,15,5,10,20,25]
    n=len(p)-1
    m={}
    s={}
    do_memoized_matrix_chain(p,m,s)
    print 'optimal parens:',
    do_print_optimal_parens(s,n)
    print 'm:',
    print_ms(m,n)
    print 's:',
    print_ms(s,n)
